package com.lw.leetcode.arr.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 2007. 从双倍数组中还原原数组
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/5 15:24
 */
public class FindOriginalArray {


    public static void main(String[] args) {
        FindOriginalArray test = new FindOriginalArray();

        //
        int[] arr = {1, 3, 4, 2, 6, 8};
        // [2,4,8,10]
//        int[] arr = {4,4,16,20,8,8,2,10};

        int[] originalArray = test.findOriginalArray(arr);

        System.out.println(Arrays.toString(originalArray));
    }

    public int[] findOriginalArray(int[] changed) {
        int length = changed.length;
        if ((length & 1) == 1) {
            return new int[0];
        }
        Arrays.sort(changed);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : changed) {
            map.merge(i, 1, (a, b) -> a + b);
        }
        int[] arr = new int[length >> 1];
        int i = 0;
        for (int value : changed) {
            int c = map.get(value);
            if (c == 0) {
                continue;
            }
            map.put(value, c - 1);
            Integer c2 = map.get(value << 1);
            if (c2 != null && c2 != 0) {
                map.put(value << 1, c2 - 1);
                arr[i++] = value;
                continue;
            }
            return new int[0];
        }
        return arr;
    }

}
